import java.util.*;

/**
 * Created by zhangjinrui on 17/6/27.
 */

public class Solution373 {

    public static void main(String args[]) {
        Solution373 s = new Solution373();
        System.out.println(s.kSmallestPairs(new int[]{1, 1, 2}, new int[]{1, 2, 3}, 10));
    }

    class Pair implements Comparable<Pair> {
        int idx1;
        int idx2;
        int v;

        public Pair(int a, int b, int v) {
            this.idx1 = a;
            this.idx2 = b;
            this.v = v;
        }


        @Override
        public int compareTo(Pair o) {
            return this.v - o.v;
        }

        public int hashCode() {
            return (idx1 + "|" + idx2).hashCode();
        }

        public String toString() {
            return "[" + idx1 + "," + idx2 + "]";
        }
    }

    public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        List<int[]> ret = new ArrayList<>();
        if (nums1.length * nums2.length == 0) {
            return ret;
        }
        Arrays.sort(nums1);
        Arrays.sort(nums2);

        Queue<Pair> heap = new PriorityQueue<Pair>();
        Pair p0 = new Pair(0, 0, nums1[0] + nums2[0]);

        HashMap<Integer, Integer> mp = new HashMap<>();
        heap.add(p0);
        mp.put(p0.hashCode(), 1);

        int cnt = 0;
        while (!heap.isEmpty() && cnt < k) {
            Pair p = heap.poll();
            ret.add(new int[]{nums1[p.idx1], nums2[p.idx2]});
            if (p.idx2 + 1 < nums2.length) {
                Pair p1 = new Pair(p.idx1, p.idx2 + 1, nums1[p.idx1] + nums2[p.idx2 + 1]);
                if (!mp.containsKey(p1.hashCode())) {
                    heap.add(p1);
                    mp.put(p1.hashCode(), 1);
                }
            }

            if (p.idx1 + 1 < nums1.length) {
                Pair p1 = new Pair(p.idx1 + 1, p.idx2, nums1[p.idx1 + 1] + nums2[p.idx2]);
                if (!mp.containsKey(p1.hashCode())) {
                    heap.add(p1);
                    mp.put(p1.hashCode(), 1);
                }
            }
            cnt++;
        }
        return ret;
    }
}













